/*
 * 0100. 删除排序数组中的重复数字
 * 给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。
 * 不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。
 * https://www.lintcode.com/problem/remove-duplicates-from-sorted-array/description
 * 
 * 样例
 * 给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。
 */
package remove_duplicates_from_sorted_array_0100;

public class Remove_duplicates_from_sorted_array_0100 {
	/*
	 * @param nums: An ineger array
	 * @return: An integer
	 */
	public static int removeDuplicates(int[] nums) {
		// write your code here
		//    	int cntSum = nums.length;
		//    	for(int i = 0; i < cntSum - 1; ++i) {
		//    		for(int j = i + 1; j < cntSum; ++j) {
		//    			if(nums[i] == nums[j]) {
		//    				for(int z = j; z < cntSum - 1; ++z) {
		//    					nums[z] = nums[z + 1];
		//    					if(z == cntSum - 2) {
		//    						nums[z + 1] = nums[i];
		//    					}
		//    				}
		//    				--cntSum;
		//    			}
		//    		}
		//    	}
		//    	return cntSum;

		int cnt = 0;
		for(int i = 0; i < nums.length; ) {
			int tmpCnt = i;
			while((tmpCnt < nums.length) && (nums[i] == nums[tmpCnt])) {
				++tmpCnt;
			}
			nums[cnt++] = nums[i];
			i = tmpCnt;
		}
		return cnt;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int nums[] = {-14,-14,-13,-13,-13,-13,-13,-13,-13,-12,-12,-12,-12,-11,-10,-9,-9,-9,-8,-7,-5,-5,-5,-5,-4,-3,-3,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,1,1,1,1,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,7,8,8,8,9,9,9,10,10,10,11,11,11,12,12,12,13,14,14,14,14,15,16,16,16,18,18,18,19,19,19,19,20,20,20,21,21,21,21,21,21,22,22,22,22,22,23,23,24,25,25};
		int cnt = removeDuplicates(nums);
		for(int i = 0; i < cnt; ++i) {
			System.out.print(nums[i] + " ");
		}
		System.out.println();
	}

}
